1. Field of the Invention
The present invention generally relates to compilers for generating application-specific integrated circuits and, more particularly, to compilers for generating carry-chain structures for use in application-specific integrated circuits.
2. State of the Art
It is well known to provide integrated circuits, or "chips", of the type known as application-specific integrated circuits (ASICs). In essence, ASIC chips are custom-designed circuits of the LSI (large scale integration) or VLSI (very large scale integration) class. ASIC chips often include one or more functional blocks or "cells" which, individually, may be classified as LSI or VLSI circuits. For instance, the cells within an ASIC chip may comprise one or more random access memories (RAMs), read-only memories (ROMs), or arithmetic logic units (ALUs). Also, cells can be as simple as an individual logic gate.
To efficiently and economically design ASIC chips, it is necessary to use automated systems, usually referred to as compilers. Compilers allow circuit designers to custom design ASIC chips by drawing upon libraries containing standardized designs of circuits that can comprise cells within ASIC chips. Also, compilers can themselves include compiling sub-systems. For example, in designing an ASIC chip with a compiler, a design engineer may want a functional block to include one or more ALU circuits and, rather than designing the ALU circuits himself, the engineer may want a compiling sub-system to design the ALU circuits while including some special connections that he has specified.
Compilers can, of course, generate circuits for uses other than in ASIC chips. For instance, compiler systems can design circuits for implementation on printed circuit boards. The following emphasis on compilers that generate ASIC chips is not intended to exclude their other USES.
In view of the preceding discussion, it can be appreciated that, for compiler systems to be practical and commercially acceptable, the systems must allow circuit designers flexibility in modifying functional blocks within ASIC chips. For instance, circuit designers often want the flexibility to modify standard ALU cells to accommodate different bit widths. For such modifications to be easily accomplished by automated compilers (or compiling subsystems), the standard cells must have regular and relatively non-complex architectures. At the same time, however, the standard cells usually must be able to process data quickly, so that their host circuits are not slowed. In particular, it is usually important that ALU cells operate at high speeds.
To provide high-speed ALU circuits, it is known to include high speed adder/subtractors. One example of a high speed adder is the so-called "conditional-sum adder". Conditional-sum adders are, for example, described at chapter 4 of the text Computer Arithmetic Principles Architecture, and Design, by Kai Hwang (Wiley, 1979). As explained in that text, conditional-sum adders can be grouped to accomplish operations such as multiplication and division. Furthermore, by employing additional logic elements, the adders can be transformed into ALU circuits that perform various binary logic operations as well as arithmetic operations.
High speed operation of conditional-sum adders is primarily attributable to their generating two different carry-out bits at individual adder stages. More particularly, at various internal stages, conditional-sum adders generate a first carry-out bit based upon the assumption that the actual carry-in bit to the stage will have one binary value (e.g., high or binary 1) and, also, generate a second carry-out bit based upon the assumption that the actual carry-in bit will have a complementary binary value (e.g. low or binary 0). The first and second carry-out bits are usually referred to as either "provisional" or "conditional" carry bits, and the two terms will be used interchangeably herein.
Because provisional sums and provisional carry-out bits can be calculated at various stages of a conditional-sum adder without the stages waiting for actual carry-in bits, numerous provisional additions can be made at the same time. Thereafter, the actual carry bits can "ripple" through a conditional-sum adder at a rate which is faster than with ordinary adders.
Although conditional-sum adders provide benefits in terms of data-handling speed at high bit widths, the fact that provisional carry-out bits are generated at numerous stages in the adders results in the devices being "architecturally" complex and irregular. Moreover, the architecture of those devices renders modifications, such as bit-width modifications, difficult to accomplish. Thus, conditional-sum adders of conventional architecture cannot be readily generated by computer algorithms and, therefore, are not well suited for use by automated compiling systems.